//
// Description: 88. 合并两个有序数组
// Created by Loading on 2021/4/5.
//

#include <bits/stdc++.h>

using namespace std;

void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
    /* 起初想法开辟新空间合并完成，再将其赋值给nums1，效率低下，占用空间大 */
    /* 由于nums1后侧数据均为0，可以直接可以修改nums1数据，使用nums1与nums2比较赋值 */
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }

    //如果i还未遍历到头，则已经有序，无需操作
    //如果j还未遍历到头，直接全部赋值到至前侧，最终有序
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

int main() {
    vector<int> nums1 = {1, 2, 3, 0, 0, 0};
    vector<int> nums2 = {2, 5, 6};
    merge(nums1, 3, nums2, 3);
    for (auto &x : nums1) {
        cout << x << " ";
    }
    cout << endl;
}